package com.leetcode.题库;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 覃国强
 * @date 2022-04-13 20:28
 */
public class 题库_0116_填充每个节点的下一个右侧节点指针 {


  static
  class Solution {
    public Node connect(Node root) {
//      connectWithQueue(root);
      connectWithNoQueue(root);
      return root;
    }

    private void connectWithQueue(Node root) {
      if (root == null || root.left == null) {
        return;
      }
      Deque<Node> queue = new ArrayDeque<>();
      Node last = root;
      queue.add(root.left);
      queue.add(root.right);
      while (!queue.isEmpty()) {
        Node node = queue.remove();
        if (node != last.right) {
          node.next = queue.peek();
        } else {
          last = node;
        }
        if (node.left != null) {
          queue.add(node.left);
          queue.add(node.right);
        }
      }
    }

    private void connectWithNoQueue(Node root) {
      if (root == null) {
        return;
      }
      Node leftmost = root;
      while (leftmost.left != null) {
        Node node = leftmost;
        while (node != null) {

          node.left.next = node.right;

          if (node.next != null) {
            node.right.next = node.next.left;
          }

          node = node.next;
        }
        leftmost = leftmost.left;
      }
    }

  }



  static class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int val) {
      this.val = val;
    }

    public Node(int val, Node left, Node right, Node next) {
      this.val = val;
      this.left = left;
      this.right = right;
      this.next = next;
    }
  }

}
